package com.leetcode.August;

import javax.swing.tree.TreeNode;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Description: 从前序与中序遍历序列构造二叉树
 * @Author: Mr.Fxy
 * @CreateTime: 2024-08-03 22:53
 * 前序遍历的顺序是：根节点 -> 左子树 -> 右子树。
 * 中序遍历的顺序是：左子树 -> 根节点 -> 右子树。
 * 后序遍历的顺序是：左子树 -> 右子树 -> 根节点。
 */
public class LC105从前序与中序遍历序列构造二叉树 {
    private Map<Integer, Integer> indexMap;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        indexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, preorder.length - 1, 0,inorder.length - 1);
    }
    private TreeNode  myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right || inorder_left > inorder_right) {
            return null;
        }
        // 前序遍历的第一个节点   后序的根节点
        int i = indexMap.get(preorder[preorder_left]);//0
        TreeNode inRootIndex  = new TreeNode(preorder[preorder_left]);
        inRootIndex.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + i - inorder_left, inorder_left, i - 1);
        inRootIndex.right = myBuildTree(preorder, inorder, preorder_left + i - inorder_left + 1, preorder_right, i + 1, inorder_right);
        return inRootIndex;
    }
}
/*
*   private Map<Integer, Integer> indexMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 构建哈希表，存储中序遍历中每个节点的索引
        indexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i], i);
        }
        // 调用递归函数构建二叉树
        return myBuildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        // 基本情况：如果当前子树为空，则返回 null
        if (preorder_left > preorder_right || inorder_left > inorder_right) {
            return null;
        }

        // 获取当前子树的根节点值
        int rootValue = preorder[preorder_left];
        // 在中序遍历中查找根节点的位置
        int rootInorderIndex = indexMap.get(rootValue);

        // 创建当前子树的根节点
        TreeNode root = new TreeNode(rootValue);

        // 计算左子树的长度
        int leftSubtreeLength = rootInorderIndex - inorder_left;
        // 构建左子树
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + leftSubtreeLength, inorder_left, rootInorderIndex - 1);

        // 构建右子树
        root.right = myBuildTree(preorder, inorder, preorder_left + leftSubtreeLength + 1, preorder_right, rootInorderIndex + 1, inorder_right);

        return root;
    }*/